#include"QuickSort.h"

void Swap(int* x1, int* x2)
{
	int mid = *x1;
	*x1 = *x2;
	*x2 = mid;
}

void QuickSort_1_hoare(int* arr, int left, int right)
{
	assert(arr);
	int re = right;
	int temp = left;
	left++;
	if (left >= right) return;
	while (left < right)
	{
		while (left <= right && arr[left] < arr[temp])
		{
			left++;
		}
		while (left <= right && arr[right] > arr[temp])
		{
			right--;
		}
		Swap(&arr[left], &arr[right]);		
	}
	Swap(&arr[temp], &arr[left]);
	QuickSort_1_hoare(arr, temp, left - 1);
	QuickSort_1_hoare(arr, left+1,re);
}

void QuickSort_2_lomuto(int* arr, int left, int right)
{
	assert(arr);
	if (left >= right) return;
	int pre = left; int cur = pre+1;
	int re = right; int le = left;
	while (cur <= right)
	{
		if (arr[cur] < arr[pre]&&++le!=cur)
		{
			Swap(&arr[cur], &arr[le]);
		}
		cur++;
	}
	Swap(&arr[left], &arr[le]);
	QuickSort_2_lomuto(arr, pre, le - 1);
	QuickSort_2_lomuto(arr, le+1, re);

}